package datastructre;

public class HashTable {

    static class Entry {
        int hash;//哈希码
        Object key;//键
        Object value;
        Entry next;

        public Entry(int hash,Object key,Object value){
            this.hash = hash;
            this.key = key;
            this.value = value;
        }
    }

    Entry[] table = new Entry[16];
    int size = 0;

    Object get(int hash,Object key) {
        //与运算实现取模
        hash = hash & (this.table.length - 1);
        //有空直接填入
        if (this.table[hash] == null) {
            return null;
        }
        //没空按照链表查
        Entry entry = this.table[hash];
        while (entry != null) {
            if (entry.key.equals(key)) {
                return entry.value;
            }
            entry = entry.next;
        }
        return null;
    }


    void put(int hash,Object key,Object value) {
        hash = hash & (this.table.length-1);
        Entry newEntry = new Entry(hash,key,value);
        if (this.table[hash]==null) {
            this.table[hash] = newEntry;
        } else {
            Entry entry = this.table[hash];
            while(true) {
                //遇到已经存出过该key，覆盖
                if (entry.key.equals(key)) {
                    entry.value = value;
                    return ;
                }
                if (entry.next==null) {
                    entry.next = newEntry;
                    break;
                }
                entry = entry.next;
            }
            entry.next = newEntry;
        }
        this.size++;
    }

    Object remove(int hash,Object key) {
        int idx = hash & (this.table.length-1);
        if (table[idx] == null) {
            return null;
        }
        Entry p = table[idx];
        Entry pre = null;
        while(p!=null) {
            if (p.key.equals(key)) {
                if (pre == null) {
                    table[idx] = p.next;
                } else {
                    pre.next = p.next;
                }
                p = null;
                this.size--;
                return null;
            }
            pre = p;
            p = p.next;
        }
        return null;
    }

    public static void main(String[] args) {
        HashTable table = new HashTable();
        table.put(1,"zhang","张三");
        table.put(17,"li","李四");
        table.put(2,"wang","王五");
        System.out.println(table);

        System.out.println(table.get(1,"zhang"));
        System.out.println(table.table[1].next.value);
        table.remove(1,"zhang");
        System.out.println(table.get(1,"li"));

    }
}
